Reverse Code Engineering RCE CD +sandman 2000

home *** CD-ROM | disk | FTP | other *** search

/ Reverse Code Engineering RCE CD +sandman 2000 / ReverseCodeEngineeringRceCdsandman2000.iso / RCE / Library / Manuels & Misc / Assembly / ASM-TUT.ZIP / CHAP13.DOC < prev next >

Wrap

Text File | 1990-07-19 | 12.4 KB | 282 lines

129 CHAPTER 13 - MULTIPLE WORD ARITHMETIC II We have just done multiple word addition and subtraction, which are easy. Now we have multiplication and division. We are going to multiply and divide long numbers by a one word (2 byte) number. Multiplying multiple-word numbers by multiple-word numbers is complex and time consuming but can be done. Dividing by a multiple-word number is an entirely different ballgame.{1} We'll do unsigned numbers first, then in a later chapter add the code we need for signed numbers. The core routine is the same. UNSIGNED MULTIPLICATION If you multiply an n digit number by an m digit number, there is a possibility of n+m digits in the result. 863 is 3 digits, 4975 is 4 digits, 863 X 4975 = 4,293,425 is 7 digits = 4 + 3. We will be multiplying an 8 byte number by a 2 byte number, so we'll need 10 bytes for the possible maximum result. Here's the code: ; - - - - - - - - ENTER DATA BELOW THIS LINE multiplicand dq ? multiplier dw ? result db 10 dup (?) ; - - - - - - - - ENTER DATA ABOVE THIS LINE ; - - - - - - - - ENTER CODE BELOW THIS LINE outer_loop: lea ax, multiplicand ; load multiplicand call get_unsigned_8byte call print_unsigned_8byte call get_unsigned ; unsigned word to multiplier mov multiplier, ax lea si, multiplicand ; load pointers lea bx, result mov cx, 4 ; number of words sub di,di ; clear di mult_loop: ____________________ 1 For those of you with a hankering for large multiplication and division, I have included subroutines which can multiply and divide numbers of any length in a file called MISHMASH.DOC. It is in \EXTRAFILE. You will need to finish all the chapters before looking at it, since it uses things that you don't know about yet. ______________________ The PC Assembler Tutor - Copyright (C) 1989 Chuck Nelson The PC Assembler Tutor 130 ______________________ mov ax, [si] ; multiplicand to ax mul multiplier ; {2} add ax, di ; high word from last multiplication jnc store_result inc dx ; {3} store_result: mov [bx], ax ; store 1 word of result. mov di, dx ; save high word for next multiplication add si, 2 ; increment pointers add bx, 2 loop mult_loop mov [bx], di ; move last word of result mov ax, [bx] call print_hex lea ax, result call print_unsigned_8byte jmp outer_loop ; - - - - - - - - ENTER CODE ABOVE THIS LINE There are two different input calls, an 8 byte one and a 2 byte one. Inside the loop we store the high word from the multiplication in DI and then add it to the next result. This is the same as when you multiply single digits in base 10 (9 X 7 = 63 carry the 6). Note that when you add DI, there can be a carry from AX to DX, but there can be no carry out of DX. After we drop out of the loop, we need to put the last word in result. We take it from DI, but we could take it from DX if we wanted. Finally, the printing. Print_unsigned_8byte can't print the whole result, so we are printing the high word in hex form. If those top two bytes are non zero, what 'print_unsigned_8byte' prints will be incorrect because it is missing the top 2 bytes. Note once again that the only thing constraining this program to an 8 byte number is the 4 that we put in CX - change that number and you can do any size number that you want. Run a bunch of numbers through this, including a couple that have more than a 20 digit result. UNSIGNED DIVISION Division is done the same way in the software as it is done with pencil and paper, starting at the left and working right. On the computer, this means starting with the high order word and working down. ____________________ 2 It would be about 3% faster to have this in a register, but unfortunately we are out of registers. 3 Do we need to check DX for a carry here? No. The maximum multiplication is FFFFh X FFFFh. The result is FFFE 0001h. That means that DX is a maximum FFFEh. If you add one, that's FFFFh, and no carry occurs. Chapter 13 - Multiple Word Arithmetic II 131 ________________________________________ ; - - - - - - - - ENTER DATA BELOW THIS LINE dividend dq ? divisor dw ? quotient dq ? remainder dw ? ; - - - - - - - - ENTER DATA ABOVE THIS LINE ; - - - - - - - - ENTER CODE BELOW THIS LINE outer_loop: lea ax, dividend ; get dividend call get_unsigned_8byte call print_unsigned_8byte call get_unsigned ; get divisor mov divisor, ax lea si, dividend + 6 ; start at the top lea bx, quotient + 6 mov di, divisor mov cx, 4 ; number of words sub dx, dx ; clear dx for first division division_loop: mov ax, [si] ; dividend word to ax div di ; {4} mov [bx], ax ; word of result to quotient sub si, 2 ; decrement the pointers sub bx, 2 loop division_loop mov remainder, dx mov ax, remainder call print_unsigned lea ax, quotient call print_unsigned_8byte jmp outer_loop ; - - - - - - - - ENTER CODE ABOVE THIS LINE That's it? Yup. The division instruction is designed to work effeciently and simply. We start with the most significant digits, divide, put the quotient in the variable "quotient", ____________________ 4 After this division, the quotient is in AX and the remainder is in DX. Say, aren't we going to do anything with the remainder? There's nothing in the code about DX until we get out of the loop. In fact, we ARE doing something with the remainder. Just like division with pencil and paper, when you have a remainder, you bring it down to the left of the next digits you are going to divide. These get divided the next time around. But we don't need to move the remainder because it's already in the right place. Pretty snappy, huh? You don't need to move anything; it all takes care of itself. The PC Assembler Tutor 132 ______________________ DECREMENT the pointers, and get the next word for division. After the final division, we have the remainder left in DX, so we move it to the variable "remainder". The final instructions print the remainder and the quotient. Notice that we don't need to touch the remainder during the entire operation. The 8086 leaves it exactly where it needs to be for the next division. Using the DX register when you have single word division seems screwy, but using DX for multiple word division is both natural and elegant. The Intel people made one instruction do the work of both. Remember from the earlier chapter on division that you can get a zero divide error if the quotient is larger than 65535. Is it possible to get a quotient larger than 65535 in this routine? NO. It is impossible to get a zero divide on anything other than a zero.{5} Run the program and do several examples. You can even do a 0 divide if you feel like interrupting the program. SIGNED NUMBERS For byte or word signed multiplication and division, the 8086 changes the signed numbers into unsigned numbers, does unsigned multiplication/division, then adjusts for sign. For long numbers, we have to do these operations ourselves, so we need three sections of code. (1) change the numbers into unsigned numbers, (2) do unsigned multiplication/division and (3) adjust the signs. The routines that we have here are part two of this scheme. It will be easier to implement this once you know about subroutines, so signed division and multiplication will have to wait till later. ____________________ 5 This is technical, so if you start getting lost, don't worry about it. How do we know that it's impossible? What we are putting in DX is the remainder (R). R is always less than the divisor (D). Let Q be the number in AX the next time around. What we are dividing is: ((R*65536) + Q ) / D <= (( R*65536 ) + 65535 ) /D since Q is less than to or equal to 65535. This is the maximum. ( ((R*(65535 + 1)) + 65535 ) /D = (((R+1) * 65535) + R)/D (huh?) = ((R+1) * 65535)/D + R/D Let's do a few examples: if D = 1, R < D so R = 0 max. = (1*65535)/1 + 0/1 = 65535 rem 0 where rem = remainder. If D = 2, R < D so R = 1 max. = ((1+1)*65535)/2 + 1/2 = 65535 rem 1 If D = 3, R < D so R = 2 max. = (2+1)*65535)/3 + 2/3 = 65535 rem 2 See a pattern here? R/D < 1, so the quotient can never be 65536. The maximum will always be 65535 with the remainder 1 less than the divisor. If you aren't a techie, ignore all this. Chapter 13 - Multiple Word Arithmetic II 133 ________________________________________ SUMMARY For both signed and unsigned numbers, multiple word division and multiplication are based on an unsigned number routine. Signed numbers are changed into unsigned numbers, the operation is performed, and the signs of the results are adjusted. Multiplication is done the same as for single words except that the high word from one result is saved and added to the low word of the next result, thus adding the two partial results. If this addition gives a carry, DX must be incremented. Division operates from left to right. For the first division, DX is zeroed. After that it always contains the remainder from the last division. The quotients in AX are moved to memory one by one. At the end, the final remainder will be in DX.